#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;




class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //先用ladmda表达式排序
        sort(envelopes.begin(),envelopes.end(),[](vector<int>& A,vector<int>& B)->bool{
            if(A[0]==B[0]){
                return A[1]>B[1];
            }
            return A[0]<B[0];
        });

        //排序完成后，使用贪心策略
        vector<int> dp;
        for(int i = 0;i<envelopes.size();++i){
            if(i==0){
                dp.push_back(envelopes[i][1]);
            }
            else{
                if(envelopes[i][1]>dp.back()){
                    dp.push_back(envelopes[i][1]);
                }
                else{
                    auto it = lower_bound(dp.begin(),dp.end(),envelopes[i][1]);
                    *it = envelopes[i][1];
                }
            }
        }
        return dp.size();
    }
};


int main(){
    Solution S;
    vector<vector<int>> envelops = {{5,4},{6,4},{6,7},{2,3}};
    S.maxEnvelopes(envelops);
}